package com.leetcode.graph;

import javafx.util.Pair;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/6/16 19:17
 */
public class ShortestPathBinaryMatrix_1091 {
    public int shortestPathBinaryMatrix(int[][] grids) {
        if (grids == null || grids.length == 0 || grids[0].length == 0) {
            return -1;
        }
        // 准备8个方向的数组
        int[][] direction = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
        int high = grids.length, width = grids[0].length;

        // 通过Pair特殊的equals方法，可以判定是否已经出现过
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(0, 0));
        int pathLen = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            pathLen++;
            while (size-- > 0) {
                Pair<Integer, Integer> now = queue.poll();
                int x = now.getKey(), y = now.getValue();
                // 如果阻塞那么继续下一个循环
                if (grids[x][y] == 1) continue;
                // 如果到达了终点，返回总长度
                if (x == high - 1 && y == width - 1) return pathLen;
                // 标记为1，以后不再访问 -- 这里与常规做法不一样，原题的矩阵已经可以检查是否经过路程
                // 重点！ 通过这一步可以直接不用一个boolean数组来判定是否出现过
                grids[x][y] = 1;
                // 每次将所有的相邻点加入队列，通过以上两个判定条件依次判定
                for (int[] d : direction) {
                    int xx = x + d[0], yy = y + d[1];
                    if (xx < high && yy < width && xx >= 0 && yy >= 0)
                        queue.offer(new Pair<>(xx, yy));
                }
            }
        }
        return -1;
    }

    public int shortesetPathBinaryMatrix2(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;

        int[][] direction = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
        int m = grid.length, n = grid[0].length;
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(0, 0));
        int pathLength = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            pathLength++;
            while (size-- > 0) {
                Pair<Integer, Integer> cur = queue.poll();
                // 获取两点的坐标
                int x = cur.getKey(), y = cur.getValue();
                if (grid[x][y] == 1) continue;
                if (x == m - 1 && y == n - 1) return pathLength;
                grid[x][y] = 1;
                for (int[] d : direction) {
                    int xx = d[0] + x, yy = y + d[1];
                    if (xx < m && yy < n && xx >= 0 && yy >= 0)
                        queue.offer(new Pair<>(xx, yy));
                }
            }
        }
        return -1;
    }
}
